package org.example;

import java.util.Arrays;
import java.util.Comparator;

public class Test1 {
    //leetcode 1005 k次取反后最大化的数组 https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

    /**
     * 贪心
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int index = 0;
        while (index < n && k > 0 && nums[index] < 0) {
            nums[index] = -nums[index++];
            k--;
        }
        if (k > 0) {
            if (index >= n) {
                nums[n - 1] = (k % 2 == 0) ? nums[n - 1] : -nums[n - 1];
            }else {
                if (index > 0 && nums[index] > nums[index - 1]) {
                    nums[index - 1] = (k % 2 == 0) ? nums[index - 1] : -nums[index - 1];
                }else {
                    nums[index] = (k % 2 == 0) ? nums[index] : -nums[index];
                }
            }
        }
        int sum = 0;
        for (int x : nums) sum += x;
        return sum;
    }
}
